package com.sakura.二叉树;

import java.lang.reflect.Array;
import java.util.*;

// 二叉树上应该怎么求，二叉搜索树上又应该怎么求？
public class Code501_二叉搜索树中的众数 {

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    private static List<Integer> ans = new ArrayList<>();
    private int max = 0;
    private int count = 0;
    private TreeNode pre = null;

    public int[] findMode(TreeNode root) {
        searchBT(root);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    private void searchBT(TreeNode root) {
        if (root == null) {
            return;
        }
        searchBT(root.left);
        if (pre == null) {
            count = 1;
        } else if (pre.val == root.val) {
            count++;
        } else {
            count = 1;
        }
        if (count > max) {
            max = count;
            ans.clear();
            ans.add(root.val);
        } else if (count == max) {
            ans.add(root.val);
        }
        pre = root;
        searchBT(root.right);
    }


    // ---------------------- 二叉树 二叉搜索树通用 --------------------------------
    private final HashMap<Integer, Integer> map = new HashMap<>();

    public int[] findMode_1(TreeNode root) {
        preorder(root);
        int max = 0;
        for (Integer value : map.values()) {
            max = Math.max(max, value);
        }

        List<Integer> ans = new ArrayList<>();
        int finalMax = max;
        map.forEach((k, v) -> {
            if (v == finalMax) {
                ans.add(k);
            }
        });
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public void preorder(TreeNode cur) {
        if (cur == null) {
            return;
        }
        map.merge(cur.val, 1, Integer::sum);
        preorder(cur.left);
        preorder(cur.right);
    }
}
